#include <stdio.h>
#include <stdlib.h>

int *mergeSort(int *array, int len);
int *merge(int *array1, int len1, int *array2, int len2);
int *split(int *array, int len);

void arraycopy(int *src, int srcpos, int *dest, int destpos, int len)
{
    for (; len > 0; len--)
    {
        src[srcpos++] = dest[destpos++];
    }
}

int main()
{
    srand(time(NULL));
    int len = 10;
    int array[len];
    int i;
    for (i = 0; i < len; i++)
    {
        array[i] = rand() % 100;
    }
    for (i = 0; i < len;)
    {
        printf("%d", array[i]);
        if (++i < len)
        {
            printf(",");
        }
        else
        {
            printf("\n");
        }
    }
    int *res = split(array, len);
    printf("answer:");
    for (i = 0; i < len;)
    {
        printf("%d", res[i]);
        if (++i < len)
        {
            printf(",");
        }
        else
        {
            printf("\n");
        }
    }
    return 0;
}
int *split(int *array, int len)
{
    if (len == 1)
    {
        return array;
    }
    if (len == 2)
    {
        int temp = array[0];
        if (array[0] > array[1])
        {
            array[0] = array[1];
            array[1] = temp;
        }
        return array;
    }
    int len1 = len / 2;
    int len2 = len - len1;
    int *array1 = malloc(sizeof(int) * len1);
    int *array2 = malloc(sizeof(int) * len2);
    arraycopy(array1, 0, array, 0, len1);
    arraycopy(array2, 0, array, len1, len2);
    return merge(split(array1, len1), len1, split(array2, len2), len2);
}

int *merge(int *array1, int len1, int *array2, int len2)
{
    int len = len1 + len2;
    int *res = malloc(sizeof(int) * (len1 + len2));
    int i = 0;
    int j = 0;
    int k;

    for (k = 0; k < len; k++)
    {
        if (i < len1 && (j == len2 || array1[i] < array2[j]))
        {
            res[k] = array1[i];
            i++;
        }
        else
        {
            res[k] = array2[j];
            j++;
        }
    }

    return res;
}